//
// Created by bleedingfight on 2020/6/24.
//
#include "numSquares.h"
<<<<<<< HEAD:cxx/algorithm/src/numSquares.cc
int numSquares(int n){
    int range = sqrt(n);
    std::set<int> legal_num;
    for(int i=1;i<range+1;i++){
        legal_num.insert(pow(i,2));
    }
    int layers = 0;
    std::set<int> current_queue = std::set<int>({n});
    while(!current_queue.empty()){
        ++layers;
        std::set<int> next_queue = std::set<int>();
        for(auto elem:current_queue){
            for(auto legal:legal_num){
                if(elem == legal)
                    return layers;
                else if(elem<legal)
                    break;
                else{
                    next_queue.insert(elem-legal);
                }
            }
        }
        current_queue.swap(next_queue);
    }
    return layers;


}

=======
int numSquares(int n) {
  int range = sqrt(n);
  std::set<int> legal_num;
  for (int i = 1; i < range + 1; i++) {
    legal_num.insert(pow(i, 2));
  }
  int layers = 0;
  std::set<int> current_queue = std::set<int>({n});
  while (!current_queue.empty()) {
    ++layers;
    std::set<int> next_queue = std::set<int>();
    for (auto elem : current_queue) {
      for (auto legal : legal_num) {
        if (elem == legal)
          return layers;
        else if (elem < legal)
          break;
        else {
          next_queue.insert(elem - legal);
        }
      }
    }
    current_queue.swap(next_queue);
  }
  return layers;
}
>>>>>>> dev:cxx/algorithm/common/src/numSquares.cc
